package org.example;

public class fannkuchredux {
    public static void main(String[] args) {
        // 解析输入参数，默认n=10便于测试
        int n = args.length > 0 ? Integer.parseInt(args[0]) : 10;
        if (n < 0 || n > 12) {
            System.out.println("Invalid input (n must be between 0 and 12)");
            return;
        }

        System.out.println("开始计算FannkuchRedux(n=" + n + ")...");
        long startTime = System.currentTimeMillis();

        // 执行计算
        int[] result = fannkuch(n);

        long endTime = System.currentTimeMillis();
        long duration = (endTime - startTime) / 1000; // 转换为秒

        // 确保结果输出（核心输出部分）
        System.out.println("\n计算完成！耗时: " + duration + "秒");
        System.out.println(result[0]); // 校验和
        System.out.println("Pfannkuchen(" + n + ") = " + result[1]); // 最大翻转次数
    }

    private static int[] fannkuch(int n) {
        if (n <= 1) {
            return new int[]{0, 0};
        }

        // 计算阶乘表
        int[] fact = new int[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }
        int totalPerms = fact[n];
        System.out.println("总排列数: " + totalPerms + "，开始处理...");

        int[] p = new int[n];      // 当前排列
        int[] pp = new int[n];     // 翻转副本
        int[] count = new int[n];  // 计数数组

        // 初始化第一个排列
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }

        int maxFlips = 0;
        int checkSum = 0;

        // 遍历所有排列
        for (int idx = 0; idx < totalPerms; idx++) {
            // 打印进度（每100万次排列输出一次，避免IO频繁）
            if (idx % 1000000 == 0) {
                System.out.println("已处理: " + idx + "/" + totalPerms + " (" +
                        (idx * 100 / totalPerms) + "%)");
            }

            // 计算当前排列的翻转次数
            if (p[0] != 0) {
                System.arraycopy(p, 0, pp, 0, n);
                int flips = 1;
                int first = pp[0];

                while (pp[first] != 0) {
                    flips++;
                    int lo = 1;
                    int hi = first - 1;
                    while (lo < hi) {
                        int temp = pp[lo];
                        pp[lo] = pp[hi];
                        pp[hi] = temp;
                        lo++;
                        hi--;
                    }
                    int temp = pp[first];
                    pp[first] = first;
                    first = temp;
                }

                if (flips > maxFlips) {
                    maxFlips = flips;
                }
                checkSum += (idx % 2 == 0) ? flips : -flips;
            }

            // 生成下一个排列
            int i = 1;
            count[i]++;
            while (count[i] > i) {
                count[i] = 0;
                i++;
                if (i >= n) break;
                count[i]++;
            }
            if (i >= n) break;

            // 旋转前缀
            int first = p[0];
            for (int j = 0; j < i; j++) {
                p[j] = p[j + 1];
            }
            p[i] = first;
        }

        return new int[]{checkSum, maxFlips};
    }
}
